package edu.dayu.demo4;

/**
 * 请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
 * 输入: s = "abca"
 * 输出: true
 * 解释: 可以删除 "c" 字符 或者 "b" 字符
 *
 * 思路：首先原来是 回文的，那肯定是回文，最多删一个，组成回文。
 *      那就是在回文的思路上，多一个判断，当不相等时，去判断下一个与对面是否相等，如果一边不相等，就换一个删，两个都不想等就 false。
 */
public class 最多删除一个字符得到回文 {
    public static void main(String[] args) {
        String s = "cupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupucu";
        System.out.println(validPalindrome(s));
    }

    public static boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        int l,r;
        while (left<=right){
            l = s.charAt(left);
            r = s.charAt(right);

            if (l==r){
                left++;
                right--;
            }else{
                // 只要出现错误，就直接进行 死刑判断，也就是 去除哪一个 进行后续。
                return validPalindrome(s, left, right - 1) || validPalindrome(s, left + 1, right);
            }
        }
        return true;
    }

    public static boolean validPalindrome(String s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }

}
